/*
 * @lc app=leetcode.cn id=121 lang=cpp
 *
 * [121] 买卖股票的最佳时机
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // int n = prices.size();
        // int min_price = 1e5;
        // int ret = 0;
        // for(int i = 0;i < n;i++) {
        //     ret = max(ret,prices[i]-min_price);
        //     min_price = min(min_price,prices[i]);
        // }
        // return ret;

        int n = prices.size();
        if (n == 0){
            return 0; // 边界条件
        } 
        int minprice = prices[0];
        vector<int> dp (n, 0);
        for (int i = 1; i < n; i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};
// @lc code=end

